home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_13_03
/
grant
/
demo.cpp
< prev
next >
Wrap
C/C++ Source or Header
|
1994-12-22
|
4KB
|
145 lines
#include <stdlib.h>
#include <stdio.h>
#include "pop.h"
static enum Bool {FALSE, TRUE};
// MAXWEIGHT defines the constraint of the knapsack
// example and ItemDesc is simply the coding scheme.
static const int MAXWEIGHT = 17;
static const struct
{
int Weight;
int Value;
} ItemDesc[] = {
{3, 4}, {3, 4}, {3, 4}, {3, 4}, {3, 4},
{4, 5}, {4, 5}, {4, 5}, {4, 5},
{7, 10}, {7, 10}, {8, 11}, {8, 11}, {9, 13}};
void CalcWeightAndValue(CGAChromosome *Chromosome,
int& Weight, int& Value);
Bool FoundSolution(CGAPopulation& Pop);
void PrintPop(CGAPopulation& Pop);
// Main creates the population of chromosomes and
// continues creating new generations until a solution
// is found.
int main(void)
{
const float MaxMutationRate = 0.2;
const int PopulationSize = 30;
CGAPopulation Pop(PopulationSize, sizeof(ItemDesc) /
sizeof(ItemDesc[0]),
MaxMutationRate);
while (!FoundSolution(Pop)) {
Pop.CreateNextGeneration();
PrintPop(Pop);
}
return EXIT_SUCCESS;
}
// Print information and statistics about population.
void PrintPop(
CGAPopulation& Pop)
{
float TotalFitness = 0;
printf("Idx Fit Val Wt Chromosome\n");
for (size_t ChromIdx = 0;
ChromIdx < Pop.GetPopulationSize();
ChromIdx++) {
int Weight;
int Value;
CGAChromosome *Chromosome =
Pop.GetChromosome(ChromIdx);
TotalFitness += Chromosome->GetFitness();
CalcWeightAndValue(Chromosome, Weight, Value);
printf("%3u %4.0f %3d %3d ",
ChromIdx, Chromosome->GetFitness(),
Value, Weight);
for (size_t BitIdx = 0;
BitIdx < Chromosome->GetLength();
BitIdx++) {
printf("%1u", (*Chromosome)[BitIdx]);
}
printf("\n");
}
printf(
"Gen, Best, Avg, Worst: %4d, %6.2f, %6.2f, %6.2f\n",
Pop.GetGeneration(), Pop.GetBestFitness(),
TotalFitness / ChromIdx,
Pop.GetChromosome(ChromIdx - 1)->GetFitness());
getchar();
}
// Check if a solution has been found. By definition
// it must have a value of ANSWER (24) and not exceed
// MAXWEIGHT (17). Since the fittest chromosome could
// violate the weight constraint FoundSolution must
// search through the population of chromosomes.
Bool FoundSolution(
CGAPopulation& Pop)
{
const int ANSWER = 24;
int Weight;
int Value;
for (size_t ChromIdx = 0;
ChromIdx < Pop.GetPopulationSize();
ChromIdx++) {
CalcWeightAndValue(Pop.GetChromosome(ChromIdx),
Weight, Value);
if (Weight <= MAXWEIGHT && Value == ANSWER) {
return TRUE;
}
}
return FALSE;
}
// Calculate the fitness of each chromosome by adding
// its weight to its value then subtracting a PENALITY
// for the excess weight.
float CalcFitness(
CGAChromosome *Chromosome)
{
const float PENALITY = 3.0;
int Weight;
int Value;
CalcWeightAndValue(Chromosome, Weight, Value);
if (Weight > MAXWEIGHT) {
return Value - PENALITY * (Weight - MAXWEIGHT);
} else {
return Value;
}
}
// Calculate the weight and valueof the chromosome by
// accumulating the weight and value of each item
// whose bit in the chromosome is set true.
void CalcWeightAndValue(
CGAChromosome *Chromosome,
int& Weight,
int& Value)
{
Weight = 0;
Value = 0;
for (size_t Idx = 0; Idx < Chromosome->GetLength();
Idx++) {
if ((*Chromosome)[Idx]) {
Weight += ItemDesc[Idx].Weight;
Value += ItemDesc[Idx].Value;
}
}
}